#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 定义结构体表示背包物品
struct BagItem {
    double weight;
    double value;
    BagItem(double w, double v) : weight(w), value(v) {}
};

// 比较函数，用于按照单位重量价值从大到小排序
bool compareItems(const BagItem& a, const BagItem& b) {
    return (b.value * a.weight) > (a.value * b.weight);
}

// 背包问题求解函数，求装入背包最大价值
double maxValue(int n, double c, vector<double>& w, vector<double>& v) {
    // 将数据转换成对象数组保存
    vector<BagItem> items;
    for (int i = 0; i < n; ++i) {
        items.push_back(BagItem(w[i], v[i]));
    }
    // 对物品数组按照自定义规则排序
    sort(items.begin(), items.end(), compareItems);

    double totalValue = 0.0;

    // 按单位价值从大到小枚举每件商品
    for (const auto& item : items) {
        if (item.weight <= c) {
            // 物品可以整件装入背包
            totalValue += item.value;
            c -= item.weight;
        }
        else {
            // 物品只能部分装入背包
            double x = c / item.weight;
            totalValue += item.value * x;
            c = 0;
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<double> w = {20, 10, 30, 40, 10};
    vector<double> v = {60, 10, 120, 80, 50};
    int n = 5;
    double c = 70;
    double totalValue = maxValue(n, c, w, v);
    cout << "最大价值为: " << totalValue << endl;
    return 0;
}